package org.byteDance.l129;

/**
 * @Author yu
 * @Date 2022/3/7
 */
public class Solution {

    public static void main(String[] args) {

        TreeNode treeNode = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(9, treeNode, treeNode1);
        TreeNode treeNode3 = new TreeNode(0);
        TreeNode treeNode4 = new TreeNode(4, treeNode2, treeNode3);

        Solution solution = new Solution();
        System.out.println(solution.sumNumbers(treeNode4));

    }

    public int sumNumbers(TreeNode root) {
        return dfs4(root, 0);
    }

    public int dfs(TreeNode node, int num) {
        if (node == null) {
            return 0;
        }

        int temp = num * 10 + node.val;

        if (node.left == null && node.right == null) {
            return temp;
        }

        return dfs(node.left, temp) + dfs(node.right, temp);
    }

    public int dfs2(TreeNode node, int num) {
        if (node == null) {
            return 0;
        }

        int temp = num * 10 + node.val;

        if (node.left == null && node.right == null) {
            return temp;
        }

        return dfs2(node.left, temp) + dfs2(node.right, temp);
    }

    public int dfs3(TreeNode node, int num) {
        if (node != null && node.left == null && node.right == null) {
            return num;
        }
        int sum = num * 10 + node.val;

        return dfs3(node.left, sum) + dfs3(node.right, sum);
    }

    public int dfs4(TreeNode node, int num) {
        if (node == null) {
            return 0;
        }

        int sum = num * 10 + node.val;

        if (node.left == null && node.right == null) {
            return sum;
        }

        return dfs4(node.left, sum) + dfs4(node.right, sum);
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}